import { Sort } from "../public/Sort"
import { DefaultCompare, ICompareFunction, CompareEnum } from "../public/Utils"

/**
 * 快速排序
 * 快速排序是一种分而治之的算法。 快速排序首先将一个大数组分成两个较小的子数组：
 * 低元素和高元素。然后快速排序可以递归地对子数组进行排序。
 **/
 export class QuickSort<T> extends Sort<T> {
    constructor(array: Array<T> = [], compareFun: ICompareFunction = new DefaultCompare()) {
        super(array, compareFun)
    }
    sort(array: Array<T> = this.array, left: number = 0, right: number = array.length): Array<T> {
        if (right <= left)
            return array
        let i: number = left
        let j: number = right
        //设定一个分界值，该分界值将数组分成左右两部分
        let key = array[left]
        while (true) {
            //将小于分界值的数据集中到数组的右边边
            while (true) {
                if (i == j) break
                if (this.compare.compare(array[j], key) === CompareEnum.LESS) {
                    this.swap(array, i, j)
                    break
                }
                j--
            }

            //将大于或等于分界值的数据集中到数组左边
            while (true) {
                if (i == j) break
                if (this.compare.compare(array[i], key) === CompareEnum.BIGGER) {
                    this.swap(array, i, j)
                    break
                }
                i++
            }
            if (i == j)
                break
        }

        if (right - j > 1) {
            array = this.sort(array, j + 1, right)
        }
        if (i - left > 1) {
            array = this.sort(array, left, i)
        }
        return array
    }

}

const QuickSortTest = (): void => {
    const array = [123, 424, 637, 154, 541]
    const quickSort: QuickSort<Number> = new QuickSort<Number>(array)
    console.log(quickSort.sort(array, 0, 4));
}
QuickSortTest()